package com.c2b.algorithm.leetcode.jzoffer;

/**
 * 链表中倒数最后k个结点
 *
 * @author c2b
 * @since 2023/3/7 11:56
 */
public class JzOffer0022FindKthToTail {

    /**
     * 快慢双指针
     * <p>
     * step 1：准备一个快指针，从链表头开始，在链表上先走k步。
     * step 2：准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是k。
     * step 3：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数k个元素的位置。
     * </p>
     *
     * @param pHead ListNode类
     * @param k     int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail(final ListNode pHead, final int k) {
        // write code here
        // 快慢指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        for (int i = 0; i < k; i++) {
            if (fast != null) {
                fast = fast.next;
            } else {
                return null;
            }
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void main(final String[] args) {
        final ListNode pHead = new ListNode(3);
        pHead.next = new ListNode(1);
        pHead.next.next = new ListNode(2);
        pHead.next.next.next = new ListNode(4);
        pHead.next.next.next.next = new ListNode(5);
        final JzOffer0022FindKthToTail jzOffer0022FindKthToTail = new JzOffer0022FindKthToTail();
        System.out.println(jzOffer0022FindKthToTail.FindKthToTail(pHead, 2).val);
    }
}
